package com.rr.middle;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * https://leetcode.cn/problems/jump-game-vi/?envType=daily-question&envId=2024-02-05 跳跃游戏 VI
 */
public class MaxResult {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offerLast(0);
        for (int i = 1; i < n; i++) {
            // 这个while找出区间[i-k, i-1]的所有数
            while (queue.peekFirst() < i - k) {
                queue.pollFirst();
            }
            dp[i] = dp[queue.peekFirst()] + nums[i];
            // 这个while把那些比dp[i]小的数都移除掉
            while (!queue.isEmpty() && dp[queue.peekLast()] <= dp[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        MaxResult maxResult = new MaxResult();
        int[] nums = {1, -1, -2, 4, -7, 3};
        int k = 2;
        System.out.println(maxResult.maxResult(nums, k));
    }
}
